package com.shm.leetcode;

import java.util.Arrays;

/**
 * 825. 适龄的朋友
 * 在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。
 * <p>
 * 如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：
 * <p>
 * age[y] <= 0.5 * age[x] + 7
 * age[y] > age[x]
 * age[y] > 100 && age[x] < 100
 * 否则，x 将会向 y 发送一条好友请求。
 * <p>
 * 注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。
 * <p>
 * 返回在该社交媒体网站上产生的好友请求总数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：ages = [16,16]
 * 输出：2
 * 解释：2 人互发好友请求。
 * 示例 2：
 * <p>
 * 输入：ages = [16,17,18]
 * 输出：2
 * 解释：产生的好友请求为 17 -> 16 ，18 -> 17 。
 * 示例 3：
 * <p>
 * 输入：ages = [20,30,100,110,120]
 * 输出：3
 * 解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * n == ages.length
 * 1 <= n <= 2 * 104
 * 1 <= ages[i] <= 120
 *
 * @author SHM
 */
public class NumFriendRequests {
    public int numFriendRequests(int[] ages) {
        int n = ages.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int x = ages[i];
            for (int j = 0; j < n; j++) {
                int y = ages[j];
                if (i == j || (y <= 0.5 * x + 7) || y > x || (y > 100 && x < 100)) {
                    continue;
                }
                ans++;
            }
        }
        return ans;
    }

    /**
     * 方法一：排序 + 双指针
     * 思路与算法
     *
     * 观察题目中给定的三个条件：
     *
     * \textit{ages}[y] \leq 0.5 \times \textit{ages}[x] + 7ages[y]≤0.5×ages[x]+7
     *
     * \textit{ages}[y] > \textit{ages}[x]ages[y]>ages[x]
     *
     * \textit{ages}[y] > 100 \wedge \textit{ages}[x] < 100ages[y]>100∧ages[x]<100
     *
     * 可以发现，条件 33 是蕴含在条件 22 中的，即如果满足条件 33 那么一定满足条件 22。因此，我们当条件 11 和 22 均不满足时，用户 xx 就会向用户 yy 发送好友请求，也就是用户 yy 需要满足：
     *
     * 0.5 \times \textit{ages}[x] + 7 < \textit{ages}[y] \leq \textit{ages}[x]
     * 0.5×ages[x]+7<ages[y]≤ages[x]
     *
     * 当 \textit{ages}[x] \leq 14ages[x]≤14 时，不存在满足要求的 \textit{ages}[y]ages[y]。因此我们只需要考虑 \textit{ages}[x] \geq 15ages[x]≥15 的情况，此时满足要求的 \textit{ages}[y]ages[y] 的范围为 \big( 0.5 \times \textit{ages}[x] + 7, \textit{ages}[x] \big](0.5×ages[x]+7,ages[x]]。
     *
     * 当 \textit{ages}[x]ages[x] 增加时，上述区间的左右边界均单调递增，因此如果我们将数组 \textit{ages}ages 进行升序排序，那么就可以在遍历 \textit{ages}[x]ages[x] 的同时，使用两个指针 \textit{left}left 和 \textit{right}right 维护满足要求的 \textit{ages}[y]ages[y] 的左右边界。当 xx 向后移动一个位置时：
     *
     * 如果左边界指针 \textit{left}left 指向的元素不满足 \textit{ages}[\textit{left}] > 0.5 \times \textit{ages}[x] + 7ages[left]>0.5×ages[x]+7，那么就将左边界向后移动一个位置；
     *
     * 如果右边界指针 \textit{right}right 指向的下一个元素满足 \textit{ages}[\textit{right} + 1] \leq \textit{ages}[x]ages[right+1]≤ages[x]，那么就将右边界向后移动一个位置。
     *
     * 这样一来，[\textit{left}, \textit{right}][left,right] 就是满足年龄要求的 yy 的下标。需要注意的是，xx 本身一定在 [\textit{left}, \textit{right}][left,right] 区间内，因此 xx 发送的好友请求数，即为 [\textit{left}, \textit{right}][left,right] 区间的长度减去 11。
     *
     * 我们将每一个 xx 对应的 [\textit{left}, \textit{right}][left,right] 区间长度减去 11 进行累加，就可以得到最终的答案。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n \log n)O(nlogn)。排序需要的时间为 O(n \log n)O(nlogn)，遍历所有的 \textit{ages}[x]ages[x] 以及使用双指针维护答案区间的时间复杂度为 O(n)O(n)。
     *
     * 空间复杂度：O(\log n)O(logn)，即为排序需要使用的栈空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/friends-of-appropriate-ages/solution/gua-ling-de-peng-you-by-leetcode-solutio-v7yk/
     * @param ages
     * @return
     */
    public int numFriendRequests_1(int[] ages) {
        int n = ages.length;
        Arrays.sort(ages);
        int left = 0, right = 0, ans = 0;
        for (int age : ages) {
            if (age<15){
                continue;
            }
            while (ages[left]<=0.5*age+7){
                ++left;
            }
            while (right+1<n&&ages[right+1]<=age){
                ++right;
            }
            ans+=right-left;
        }
        return ans;
    }
}
